package Lee_code;

public class Lee_213 {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int[] dp = new int[len];

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        //不考虑最后一个
        int[] dp1;
        dp1 = dp.clone();
        for (int i = 2; i<len-1; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
        }

        //不考虑第一个
        int[] dp2 = new int[len];
        dp2 = dp.clone();
        dp2[1] = dp[1];
        dp2[2] = Math.max(nums[2], nums[1]);
        for (int i = 2; i<len; i++) {
            dp2[i] = Math.max(dp2[i-1], dp2[i-2] + nums[i-1]);
        }

        return Math.max(dp1[len-2], dp2[len-1]);
    }
}
